﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using NEH_SA.Model;
using NEH_SA.Utilities;

namespace NEH_SA.GA
{
    public class GA
    {


        public static Rozwiązanie WygenerujRozwiązanie(Rozwiązanie nehResult, Problem problem)
        {
            var rand = new Random();

            var bestPermutation = Tools.GenerujPoczątkowąPermutacje(problem.LiczbaZadań, rand);
            var bestCMax = bestPermutation.ObliczCMax(problem);

            //var bestPermutation = nehResult.Permutacja;
            //var bestCMax = nehResult.CMax;

            int numberOfGenerations = problem.LiczbaMaszyn * problem.LiczbaZadań * 4;
            int populationSize = CalculatePopulationSize(problem.LiczbaZadań);
            const double crossoverProb = 0.4;
            const double mutationProb = 0.01;

            List<Chromosom> population = GetInitialPopulation(bestPermutation, rand, populationSize, problem);

            for (int i = 0; i < numberOfGenerations + 1; i++)
            {
                population.Sort((chromosom1, chromosom2) => chromosom1.Fitness.CompareTo(chromosom2.Fitness));
                var osobnikiDoRozrodu = WybierzMetodąRuletki(population, rand);
                var nowePokolenie = new List<Chromosom>(populationSize);

                foreach (Tuple<int, int> t in osobnikiDoRozrodu)
                {
                    Chromosom osobnik1;
                    Chromosom osobnik2;
                    //cross
                    if (crossoverProb <= rand.NextDouble())
                    {
                        var tuple = MixGens(population[t.Item1].Geny, population[t.Item2].Geny, rand);
                        osobnik1 = tuple.Item1;
                        osobnik2 = tuple.Item2;
                    }
                    else
                    {
                        osobnik1 = population[t.Item1];
                        osobnik2 = population[t.Item2];
                    }

                    //mutation
                    if (mutationProb <= rand.NextDouble())
                    {

                        osobnik1.Geny = osobnik1.Geny.Move(rand); //LocalSwap(rand);
                    }
                    if (mutationProb <= rand.NextDouble())
                    {
                        osobnik2.Geny = osobnik2.Geny.Move(rand); //LocalSwap(rand);
                    }
                    osobnik1.Fitness = osobnik1.Geny.ObliczCMax(problem);
                    osobnik2.Fitness = osobnik2.Geny.ObliczCMax(problem);
                    nowePokolenie.Add(osobnik1);
                    nowePokolenie.Add(osobnik2);
                }
                population = nowePokolenie;

                var localBest = population.OrderBy(chromosom => chromosom.Fitness).First();
                if (localBest.Fitness < bestCMax)
                {
                    bestPermutation = localBest.Geny;
                    bestCMax = localBest.Fitness;
                }
            }

            return new Rozwiązanie(bestPermutation, bestCMax, problem.Nazwa, Algorytm.Ga);
        }



        private static Tuple<Chromosom, Chromosom> MixGens(List<int> genyA, List<int> genyB, Random rand)
        {
            var longestCommon = GetLongestCommonSubSequence(genyA, genyB, rand);
            var onlyA = new Queue<int>(genyA.Except(longestCommon));
            var onlyB = new Queue<int>(genyB.Except(longestCommon));
            var potomekA = new int[genyA.Count];
            var potomekB = new int[genyB.Count];
            for (int i = 0; i < genyA.Count; i++)
            {
                //A
                if (longestCommon.Contains(genyA[i]))
                    potomekA[i] = genyA[i];
                else
                    potomekA[i] = onlyB.Dequeue();

                //B
                if (longestCommon.Contains(genyB[i]))
                    potomekB[i] = genyB[i];
                else
                    potomekB[i] = onlyA.Dequeue();
            }

            return new Tuple<Chromosom, Chromosom>(new Chromosom(potomekA.ToList()), new Chromosom(potomekB.ToList()));
        }

        private static List<int> GetLongestCommonSubSequence(List<int> genyA, List<int> genyB, Random rand)
        {
            var lists = new List<List<int>>();
            for (int i = 0; i < genyA.Count; i++)
            {
                lists.Add(new List<int>());
                var lastIndex = i;
                for (int j = i; j < genyA.Count; j++)
                {
                    var index = genyB.IndexOf(genyA[j]);
                    if (index >= j && index >= lastIndex)
                    {
                        lists[i].Add(genyB[index]);
                        lastIndex = index;
                    }
                }

            }
            var firstGroup = lists.GroupBy(ints => ints.Count).OrderByDescending(grouping => grouping.Key).First().ToList();
            if (firstGroup.Count > 1)
            {
                return firstGroup[rand.Next(0, firstGroup.Count - 1)];
            }
            return firstGroup.First();

        }

        private static IEnumerable<Tuple<int, int>> WybierzMetodąRuletki(List<Chromosom> population, Random rand)
        {
            var result = new List<Tuple<int, int>>();
            var sum = (double)population.Sum(chromosom => chromosom.Fitness);
            var probabilities = new List<double>();
            probabilities.Add(population[0].Fitness / sum);
            for (int i = 1; i < population.Count; i++)
            {
                probabilities.Add(probabilities.Last() + population[i].Fitness / sum);
            }
            for (int i = 0; i < population.Count / 2; i++)
            {
                result.Add(new Tuple<int, int>(GetElement(probabilities, rand.NextDouble()), GetElement(probabilities, rand.NextDouble())));
            }
            return result;
        }

        private static int GetElement(List<double> probabilities, double random)
        {
            for (int i = 0; i < probabilities.Count; i++)
            {
                if (random <= probabilities[i])
                {
                    return i;
                }
            }
            return 0;
        }


        private static List<Chromosom> GetInitialPopulation(List<int> bestPermutation, Random rand, int populationSize, Problem problem)
        {
            var liczbaZadań = bestPermutation.Count;
            var result = new List<Chromosom>(populationSize) { new Chromosom(bestPermutation.ToList()) };
            result[0].Fitness = result[0].Geny.ObliczCMax(problem);
            for (int i = 1; i < populationSize; i++)
            {
                result.Add(new Chromosom(Tools.GenerujPoczątkowąPermutacje(liczbaZadań, rand)));
                result[i].Fitness = result[i].Geny.ObliczCMax(problem);
            }

            return result;
        }

        private static int CalculatePopulationSize(int liczbaZadań)
        {
            var result = 20 + (int)Math.Floor(100 * (1 - Math.Pow(Math.E, -0.01 * liczbaZadań)));
            if (result % 2 != 0)
                result--;
            return result;
        }
    }
    public class Chromosom
    {
        public Chromosom(List<int> geny)
        {
            Geny = geny;
        }

        public List<int> Geny { get; set; }
        public int Fitness { get; set; }

    }
}
